class Solution(object):
    def exist(self, board, word):
        m = len(board)
        n = len(board[0])
        def recursion(k, p, q, occupied):
            if k == len(word):
                return True
            else:
                if p >= m or q >= n or p < 0 or q < 0 or [p, q] in occupied:
                    return False
                else:
                    occupied.append([p, q])
                    if word[k] == board[p][q]:
                        return recursion(k + 1, p + 1, q, occupied.copy()) or recursion(k + 1, p, q + 1, occupied.copy()) or recursion(k + 1, p - 1, q, occupied.copy()) or recursion(k + 1, p, q - 1, occupied.copy())
                    else:
                        return False
        flag = False
        for i in range(m):
            for j in range(n):
                flag = recursion(0, i, j, [])
                if flag:
                    break
            if flag:
                break
        return flag

data = Solution()
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCB"
print(data.exist(board, word))